﻿#ifndef _LIST_LIST_HPP
#define _LIST_LIST_HPP

// list.hpp
// 创建者：刘文豪
// 创建时间：2025/7/3
// 功能描述：实现STL链表功能
namespace mycontainer
{
    template <typename T>
    struct ListNode
    {
        ListNode()
        {
        }

        ListNode(const T &val)
            : m_val(val), m_pre(nullptr), m_next(nullptr)
        {
        }

        ListNode(const T &val, ListNode *pre, ListNode *next)
            : m_val(val), m_pre(pre), m_next(next)
        {
        }

        using Self = ListNode<T>;
        T m_val;
        Self *m_pre;
        Self *m_next;
    };

    template <typename T>
    class BidirectionalIterator
    {
    public:
        using Self = BidirectionalIterator<T>;

        BidirectionalIterator(ListNode<T> *node = nullptr)
            : m_node(node)
        {
        }

        T operator*() const
        {
            return m_node->m_val;
        }
        T *operator->() const
        {
            return &m_node->m_val;
        }
        Self &operator++()
        {
            m_node = m_node->m_next;
            return *this;
        }
        Self &operator--()
        {
            m_node = m_node->m_pre;
            return *this;
        }
        Self operator++(int)
        {
            Self temp = *this;
            m_node = m_node->m_next;
            return temp;
        }
        Self operator--(int)
        {
            Self temp = *this;
            m_node = m_node->m_pre;
            return temp;
        }
        bool operator==(const Self &other) const
        {
            return m_node == other.m_node;
        }
        bool operator!=(const Self &other) const
        {
            return m_node != other.m_node;
        }

        ListNode<T> *m_node;
    };

    template <typename T>
    class ConstBidirectionalIterator
    {
    public:
        using Self = ConstBidirectionalIterator<T>;
        ConstBidirectionalIterator(ListNode<T> *node = nullptr)
            : m_node(node)
        {
        }
        const T operator*() const
        {
            return m_node->m_val;
        }
        const T *operator->() const
        {
            return &m_node->m_val;
        }
        Self &operator++()
        {
            m_node = m_node->m_next;
            return *this;
        }
        Self &operator--()
        {
            m_node = m_node->m_pre;
            return *this;
        }
        Self operator++(int)
        {
            Self temp = *this;
            m_node = m_node->m_next;
            return temp;
        }
        Self operator--(int)
        {
            Self temp = *this;
            m_node = m_node->m_pre;
            return temp;
        }
        bool operator==(const Self &other) const
        {
            return m_node == other.m_node;
        }
        bool operator!=(const Self &other) const
        {
            return m_node != other.m_node;
        }

        ListNode<T> *m_node;
        
    };

    template <typename T>
    class ReverseBidirectionalIterator
    {
    public:
        using Self = ReverseBidirectionalIterator<T>;
        ReverseBidirectionalIterator(ListNode<T> *node = nullptr)
            : m_node(node)
        {
        }
        T operator*() const
        {
            return m_node->m_val;
        }
        T *operator->() const
        {
            return &m_node->m_val;
        }
        Self &operator++()
        {
            m_node = m_node->m_pre;
            return *this;
        }
        Self &operator--()
        {
            m_node = m_node->m_next;
            return *this;
        }
        Self operator++(int)
        {
            Self temp = *this;
            m_node = m_node->m_pre;
            return temp;
        }
        Self operator--(int)
        {
            Self temp = *this;
            m_node = m_node->m_next;
            return temp;
        }
        bool operator==(const Self &other) const
        {
            return m_node == other.m_node;
        }
        bool operator!=(const Self &other) const
        {
            return m_node != other.m_node;
        }

        ListNode<T> *m_node;
        
    };

    template <typename T>
    class ConstReverseBidirectionalIterator
    {
    public:
        using Self = ConstReverseBidirectionalIterator<T>;
        ConstReverseBidirectionalIterator(ListNode<T> *node = nullptr)
            : m_node(node)
        {
        }
        const T operator*() const
        {
            return m_node->m_val;
        }
        const T *operator->() const
        {
            return &m_node->m_val;
        }
        Self &operator++()
        {
            m_node = m_node->m_pre;
            return *this;
        }
        Self &operator--()
        {
            m_node = m_node->m_next;
            return *this;
        }
        Self operator++(int)
        {
            Self temp = *this;
            m_node = m_node->m_pre;
            return temp;
        }
        Self operator--(int)
        {
            Self temp = *this;
            m_node = m_node->m_next;
            return temp;
        }
        bool operator==(const Self &other) const
        {
            return m_node == other.m_node;
        }
        bool operator!=(const Self &other) const
        {
            return m_node != other.m_node;
        }

        ListNode<T> *m_node;
        
    };

    template <typename T>
    class List
    {
    public:
        using Iterator = BidirectionalIterator<T>;
        using ConstIterator = ConstBidirectionalIterator<T>;
        using ReverseIterator = ReverseBidirectionalIterator<T>;
        using ConstReverseIterator = ConstReverseBidirectionalIterator<T>;

        List()
        {
            m_phead = new ListNode<T>();
            m_phead->m_pre = m_phead;
            m_phead->m_next = m_phead;
            m_size = 0;
        }

        ~List()
        {
            ListNode<T> *current = m_phead->m_next;
            while (current != m_phead)
            {
                ListNode<T> *nextNode = current->m_next;
                delete current;
                current = nextNode;
            }
            delete m_phead;
            m_phead = nullptr;
            m_size = 0;
        }

        Iterator begin()
        {
            return Iterator(m_phead->m_next);
        }

        Iterator end()
        {
            return Iterator(m_phead);
        }

        ReverseIterator rbegin()
        {
            return ReverseIterator(m_phead->m_pre);
        }

        ReverseIterator rend()
        {
            return ReverseIterator(m_phead);
        }

        Iterator insert(Iterator pos, const T &val)
        {
            ListNode<T> *newNode = new ListNode<T>(val);
            Iterator cur = begin();
            while (cur != end())
            {
                if (cur == pos)
                    break;
                ++cur;
            }

            if (pos != end() && cur == end())
                return end();

            ListNode<T>* next = pos.m_node->m_next;
            newNode->m_pre = pos.m_node;
            newNode->m_next = next;
            pos.m_node->m_next = newNode;
            next->m_pre = newNode;

            m_size++;

            return Iterator(newNode);
        }

        Iterator erase(Iterator pos)
        {
            Iterator cur = begin();
            while (cur != end())
            {
                if (cur == pos)
                    break;
                ++cur;
            }

            if (cur == end())
                return end();

            ListNode<T> *nodeToDelete = pos.m_node;
            ListNode<T> *next = pos.m_node->m_next;
            ListNode<T>* pre = pos.m_node->m_pre;

            pre->m_next = next;
            next->m_pre = pre;

            delete nodeToDelete;

            m_size--;

            return next;
        }

        void push_back(const T &val)
        {
            insert(Iterator(m_phead->m_pre), val);
        }

        void push_front(const T &val)
        {
            insert(Iterator(m_phead), val);
        }

        void pop_back()
        {
            if (empty())
                return;

            erase(Iterator(m_phead->m_pre));
        }

        void pop_front()
        {
            if (empty())
                return;

            erase(begin());
        }

        bool empty() const
        {
            return m_size == 0;
        }

        size_t size() const
        {
            return m_size;
        }

    protected:
    private:
        ListNode<T> *m_phead;
        size_t m_size = 0;
    };
}

#endif // _LIST_LIST_HPP
